package special;

import org.junit.Test;

/**
 * @className: LeetCode_287
 * @Description: ...
 * @author: kunkun
 * @date: 2025/3/12 22:11
 */
public class LeetCode_287 {

    public int findDuplicate(int[] nums) {
        return solution_2(nums);
    }

    @Test
    public void test(){
        System.out.println(findDuplicate(new int[]{1, 3, 4, 2, 2}));//2
//        System.out.println(findDuplicate(new int[]{2,5,9,6,9,3,8,9,7,1}));//9
    }

    /**
     * @Author kunkun
     * @Description 方法1：快慢指针，判断是否有环
     * @Date 22:36 2025/3/12
     * @Param
     * @return
     **/
    private int solution_1(int[] nums) {
        
        int fast=0,slow=0;

        //循环直至二者相遇
        do{
            slow=nums[slow];//slow走一步
            fast = nums[nums[fast]];//fast走两步
        }while (fast!=slow);

        //一个从0出发，一个从相遇点出发
        slow=0;
        while (fast!=slow){
            slow=nums[slow];//slow走一步
            fast=nums[fast];//fast走一步
        }

        return fast;

    }

    /**
     * @Author kunkun
     * @Description 方法2：二分
     * @Date 9:10 2025/3/13
     * @Param
     * @return
     **/
    private int solution_2(int[] nums){
        int l=1,r= nums.length;
        int res=-1;
        while (l<=r){
            int mid = (l+r)>>1;
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i]<=mid){
                    count++;
                }
            }
            if (count<=mid){
                l=mid+1;
            }else {
                r=mid-1;
                res=mid;
            }
        }
        return res;
    }

}
